﻿#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
using namespace std;

#include <list>
#include <queue>
#include <unordered_map>

struct TreeNode 
{
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode() : val(0), left(nullptr), right(nullptr) {}
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
	TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

class Solution
{
public:
	vector<int> largestValues(TreeNode* root)
	{
		vector<int> ret;
		if (root == nullptr) return ret;
		queue<TreeNode*> q;
		q.push(root);
		while (q.size())
		{
			int sz = q.size();
			int tmp = INT_MIN;
			for (int i = 0; i < sz; i++)
			{
				auto t = q.front();
				q.pop();
				tmp = max(tmp, t->val);
				if (t->left) q.push(t->left);
				if (t->right) q.push(t->right);
			}
			ret.push_back(tmp);
		}
		return ret;
	}
};

int main()
{
	TreeNode* root = new TreeNode(1);

	root->left = new TreeNode(3);
	root->left->left = new TreeNode(5);
	root->left->right = new TreeNode(3);

	root->right = new TreeNode(2);
	root->right->right = new TreeNode(9);

	auto v = Solution().largestValues(root);

	for (const auto& e : v)
		cout << e << " ";

	delete root->right->right;
	delete root->right;

	delete root->left->right;
	delete root->left->left;
	delete root->left;

	delete root;

	return 0;
}